Міністерство освіти і науки України
Національний Університет „Львівська політехніка”
Інститут прикладної математики і фундаментальних наук
Кафедра прикладної математики
Курсова робота
Тема: Теорія графів
Виконав:
студент групи ПМ – 32
Львів 2008
Завдання: Знайти найкоротший шлях для графа, заданого списком, де вага кожної дуги l(u) = l(xi, xj) = ((i+j)/2+2) – ціла частина.
Код програми:
‘Опис глобальних змінних
Dim arrX(0 To 25, 1 To 2), arrY(0 To 25, 1 To 2) As Single
Dim MatrSumizh(0 To 25, 0 To 25) As Byte
Dim Max As Long
Dim MatrVidst(0 To 25, 0 To 25) As Integer
Dim Index(0 To 25) As Long
Option Explicit
Private Sub Command1_Click()
‘Відображення графа
Picture1.Scale (-50, 50)-(50, -50)
Picture1.DrawWidth = 5
Dim x As Byte
For x = 0 To 25
Picture1.PSet (40 * Cos(6.28 / 26 * x), 40 * Sin(6.28 / 26 * x))
arrX(x, 1) = 40 * Cos(6.28 / 26 * x)
arrX(x, 2) = 40 * Sin(6.28 / 26 * x)
Picture1.CurrentX = 45 * Cos(6.28 / 26 * x)
Picture1.CurrentY = 45 * Sin(6.28 / 26 * x)
Picture1.Print "X " & x
arrY(x, 1) = Picture1.CurrentX
arrY(x, 2) = Picture1.CurrentY
Next x
‘Відображення шляхів
Dim i, j As Byte
Picture1.DrawWidth = 1
For i = 0 To 25
For j = 0 To 25
If MatrSumizh(i, j) = 1 Then
Picture1.Line (arrX(i, 1), arrX(i, 2))-(arrX(j, 1), arrX(j, 2))
End If
Next j
Next i
End Sub
Private Sub Command2_Click()
Command2.Enabled = False
‘Перевірка правильності введення вершин
Dim vntr
If (CByte(Text1.Text) < 0 Or CByte(Text1.Text) > 25 Or CByte(Text2.Text) < 0 Or _
CByte(Text2.Text) > 25 Or CByte(Text1.Text) = CByte(Text2.Text)) Then
vntr = MsgBox("Введіть правильно вершини", vbCritical, "Помилка")
Exit Sub
End If
Dim i, j As Byte
For i = 0 To 25
For j = 0 To 25
MatrSumizh(i, j) = 0
Next j
Next i
MatrSumizh(1, 4) = 1: MatrSumizh(4, 1) = 1: MatrSumizh(1, 5) = 1: MatrSumizh(5, 1) = 1
MatrSumizh(2, 13) = 1: MatrSumizh(13, 2) = 1: MatrSumizh(2, 14) = 1: MatrSumizh(14, 2) = 1
MatrSumizh(3, 21) = 1: MatrSumizh(21, 3) = 1: MatrSumizh(3, 25) = 1: MatrSumizh(25, 3) = 1
MatrSumizh(4, 10) = 1: MatrSumizh(10, 4) = 1: MatrSumizh(4, 11) = 1: MatrSumizh(11, 4) = 1
MatrSumizh(4, 12) = 1: MatrSumizh(12, 4) = 1: MatrSumizh(5, 12) = 1: MatrSumizh(12, 5) = 1
MatrSumizh(5, 19) = 1: MatrSumizh(19, 5) = 1: MatrSumizh(5, 20) = 1: MatrSumizh(20, 5) = 1
MatrSumizh(6, 4) = 1: MatrSumizh(4, 6) = 1: MatrSumizh(6, 5) = 1: MatrSumizh(5, 6) = 1
MatrSumizh(7, 13) = 1: MatrSumizh(13, 7) = 1: MatrSumizh(7, 14) = 1: MatrSumizh(14, 7) = 1
MatrSumizh(8, 16) = 1: MatrSumizh(16, 8) = 1: MatrSumizh(8, 18) = 1: MatrSumizh(18, 8) = 1
MatrSumizh(18, 9) = 1: MatrSumizh(9, 18) = 1: MatrSumizh(10, 14) = 1: MatrSumizh(14, 10) = 1
MatrSumizh(11, 16) = 1: MatrSumizh(16, 11) = 1: MatrSumizh(11, 22) = 1: MatrSumizh(22, 11) = 1
MatrSumizh(11, 17) = 1: MatrSumizh(17, 11) = 1: MatrSumizh(11, 18) = 1: MatrSumizh(18, 11) = 1
MatrSumizh(12, 8) = 1: MatrSumizh(8, 12) = 1: MatrSumizh(12, 9) = 1: MatrSumizh(9, 12) = 1
MatrSumizh(9, 13) = 1: MatrSumizh(13, 9) = 1: MatrSumizh(15, 25) = 1: MatrSumizh(25, 15) = 1
MatrSumizh(16, 22) = 1: MatrSumizh(22, 16) = 1: MatrSumizh(23, 17) = 1: MatrSumizh(17, 23) = 1
MatrSumizh(15, 17) = 1: MatrSumizh(17, 15) = 1: MatrSumizh(17, 21) = 1: MatrSumizh(21, 17) = 1
MatrSumizh(18, 23) = 1: MatrSumizh(23, 18) = 1: MatrSumizh(18, 24) = 1: MatrSumizh(24, 18) = 1
MatrSumizh(19, 11) = 1: MatrSumizh(11, 19) = 1: MatrSumizh(19, 17) = 1: MatrSumizh(17, 19) = 1
MatrSumizh(19, 24) = 1: MatrSumizh(24, 19) = 1: MatrSumizh(20, 24) = 1: MatrSumizh(24, 20) = 1
MatrSumizh(20, 21) = 1: MatrSumizh(21, 20) = 1: MatrSumizh(20, 9) = 1: MatrSumizh(9, 20) = 1
MatrSumizh(0, 1) = 1: MatrSumizh(1, 0) = 1: MatrSumizh(0, 11) = 1: MatrSumizh(11, 0) = 1
MatrSumizh(0, 13) = 1: MatrSumizh(13, 0) = 1: MatrSumizh(0, 20) = 1: MatrSumizh(20, 0) = 1
‘Матриця відстаней
For i = 0 To 25
For j = 0 To 25
If MatrSumizh(i, j) = 1 Then
MatrVidst(i, j) = Int((i + j) / 2 + 2)
End If
Max = Max + MatrVidst(i, j)
Next j
Next i
‘Масив індексів...
